package com.hspedu.newData.dmsxl.树.公共祖先;

import com.hspedu.newData.dmsxl.ds.TreeNode;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-19 
 * @Version: 1.0
 */

public class LC235二叉搜索树的最近公共祖先 {

    // 递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if (root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }

    // 迭代
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {

        while (true){
            if (root.val > p.val && root.val>q.val){
                root = root.left;
            } else if (root.val < p.val && root.val < q.val) {
                root = root.right;
            }else {
                break;
            }
        }
        return root;
    }

}
